﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Demo.Framework.DataStructures
{
    class BinarySearchTree<TKey, TValue>
        where TKey : IComparable        
    {
        private BTreeNode<TKey, TValue> _root;

        /// <summary>
        /// No of comparisons : Depth of Node + 1
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public TValue Get(TKey key)
        {
            var current = _root;
            while (current != null)
            {
                if (current.Key.Equals(key))
                    return current.Value;
                else if (IsLess(current.Key, key))
                    current = current.Left;
                else
                    current = current.Right;
            }
            return default(TValue);
        }

        /// <summary>
        /// No of Comparisons : Depth of Node + 1
        /// </summary>
        /// <param name="key"></param>
        /// <param name="value"></param>
        /// <returns></returns>
        public bool Put(TKey key, TValue value)
        {
            _root = Put(_root, key, value);
            return true;
        }

        private BTreeNode<TKey, TValue> Put(BTreeNode<TKey, TValue> node, TKey key, TValue value)
        {
            if (node == null)
                return new BTreeNode<TKey, TValue>(key, value);
            if (node.Key.Equals(key))
                node.Value = value;
            else if (IsLess(node.Key, key))
                node = Put(node.Left, key, value);
            else
                node = Put(node.Right, key, value);

            node.Count = 1 + Size(node.Left) + Size(node.Right);
            return node;
        }

        /// <summary>
        /// Go left till a leaft is hit
        /// </summary>
        /// <returns></returns>
        public TKey Min()
        {
            var min = Min(_root);
            return min.Key;
        }

        private BTreeNode<TKey, TValue> Min(BTreeNode<TKey, TValue> node)
        {
            if (node.Left == null) return node;
            return Min(node.Left);
        }

        /// <summary>
        /// Go right till a leaf is hit
        /// </summary>
        /// <returns></returns>
        public TKey Max()
        {
            if (_root == null) return default(TKey);

            var current = _root;
            while (current.Right != null)
            {
                current = current.Right;
            }
            return current.Key;
        }

        /// <summary>
        /// Smallest element in tree compared to Key k
        /// 1. If Node > k, floor must be on the left
        /// 2. if Node < k, floor must be on the right
        ///     (if any key < k in right sub tree)
        /// 3. Else floor = key in root
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public TKey Floor(TKey key)
        {
            var node = Floor(_root, key);
            if (node == null)
                return default(TKey);
            else
                return node.Key;
        }

        private BTreeNode<TKey, TValue> Floor(BTreeNode<TKey, TValue> node, TKey key)
        {
            if (node == null) return null;

            if (node.Key.Equals(key)) return node;
            else if (IsLess(node.Key, key))
                return Floor(node.Left, key);
            else
            {
                var floor = Floor(node.Right, key);
                if (floor == null)
                    return floor;
                else
                    return node;
            }           
        }

        /// <summary>
        /// Size of tree
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public int Size()
        {
            return Size(_root);
        }

        private int Size(BTreeNode<TKey, TValue> node)
        {
            if (node == null) return 0;
            return node.Count;            
        }        

        #region "Traversals"
        public Queue<TKey> GetKeys(TreeTraversal mode)
        {
            var queue = new Queue<TKey>();
            switch (mode)
            {
                case TreeTraversal.InOrder:
                    InOrderTraversal(_root, queue);
                    break;
                case TreeTraversal.PreOrder:
                    break;
                case TreeTraversal.PostOrder:
                    break;
                default:
                    break;
            }

            return queue;
        }

        /// <summary>
        /// InOrderTraversals - Yields Keys in Ascending Order
        /// Left, Centre , Right
        /// </summary>
        private void InOrderTraversal(BTreeNode<TKey, TValue> node, Queue<TKey> queue)
        {
            if (node == null) return;
            InOrderTraversal(node.Left, queue);
            queue.Enqueue(node.Key);
            InOrderTraversal(node.Right, queue);
        }

        /// <summary>
        /// Centre, Left, Right
        /// </summary>
        private void PreOrderTraversal(BTreeNode<TKey, TValue> node, Queue<TKey> queue)
        {
            if (node == null) return;
            queue.Enqueue(node.Key);
            PreOrderTraversal(node.Left, queue);
            PreOrderTraversal(node.Right, queue);
        }

        /// <summary>
        /// Post Order Traversal
        /// Left, Right, Centre
        /// </summary>
        private void PostOrderTraversal(BTreeNode<TKey, TValue> node, Queue<TKey> queue)
        {
            if (node == null) return;
            PostOrderTraversal(node.Left, queue);
            PostOrderTraversal(node.Right, queue);
            queue.Enqueue(node.Key);
        }
        #endregion        

        //public bool Delete(TKey key)
        //{ }

        protected bool IsLess(TKey x, TKey y)
        {
            return x.CompareTo(y) == -1 ? true : false;
        }

        #region Delete
        /// <summary>
        /// Hibbard Deletion
        /// Case 0 - If key is a leaf (no child). Set parent's child reference to null
        /// Case 1 - If key has one child. Replace the parent link with child link
        /// Case 2 - If key has two children.
        ///     Find successor of the key (Min in the right children)
        ///     Delete the key
        ///     Replace key with successor
        /// </summary>
        /// <param name="key"></param>
        public void Delete(TKey key)
        {
            Delete(key, _root);
        }

        public BTreeNode<TKey, TValue> Delete(TKey key, BTreeNode<TKey, TValue> node)
        {
            if (node == null) return null;

            if (key.Equals(node.Key))
            {
                if (node.Right == null) return node.Left;
                if (node.Left == null) return node.Right;

                var successor = Min(node.Right);
                successor.Right = DeleteMin(node.Right);
                successor.Left = node.Left;
            }
            else if (IsLess(key, node.Key))
                node.Left = Delete(key, node.Left);
            else
                node.Right = Delete(key, node.Right);

            node.Count = 1 + Size(node.Left) + Size(node.Right);
            return node;
        }

        public BTreeNode<TKey, TValue> DeleteMin(BTreeNode<TKey, TValue> node)
        {
            if (node == null) return node.Right;

            node.Left = DeleteMin(node.Left);
            node.Count = 1 + Size(node.Left) + Size(node.Right);
            return node;
        }
        #endregion        
    }
}
